14 de julio de 2016

Objetivos

  • Estudiar la incertidumbre que presentan partidas de StarCraft, el clásico juego de estrategia en tiempo real.
  • Paso previo a la optimización con incertidumbre: vamos a estudiarla primero.
  • La incertidumbre es un factor "aleatorio", ya que está fuera de control.
  • El tiempo de partida es un factor clave. Aunque veremos que hay más factores importantes.

Partes del desarrollo

  • Matemáticas: Aprendizaje estadístico
  • Informática: R + MariaDB (SQL)

Matemáticas

Aprendizaje estadístico

  • Rama de las matemáticas que estudia el aprendizaje desde datos utlizando técnicas estadísticas.
  • Espacio de entrada \(\mathcal{X} \in \mathbb{R}^d\)
  • Espacio de salida \(\mathcal{Y}\)
  • Función objetivo desconocida \(f:\mathcal{X} \rightarrow \mathcal{Y}\)
  • \(\{(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)\} \subset \mathcal{X} \times \mathcal{Y} \mid f(x_i) = y_i\)
  • Buscar una función \(g \in \mathcal{H} \mid g \approx f\)

Aprendizaje estadístico

  • Regresión: Se busca una relación entre la variable dependiente y la independiente.
  • Clasificación: Se busca una función que para una entrada, le asigne una etiqueta. En problemas binarios, esta etiqueta suele ser -1 o 1.
  • Estimación de densidad: Similar a clasificación, pero el objetivo no es dar una clase, sino la probabilidad de pertenecer a dicha clase.

Ejemplo

Ejemplo clasificado

\(g = \text{signo}(X2 - (5.8836615)X1 - (-2.366914))\)

Ingeniería Informática

Datos disponibles

  • 6 bases de datos relacionales.
  • Más de 4000 partidas.
  • Meter imagen.

Distribución de la duración de partidas

Distribución de la duración de partidas < 75000

Componentes de una partida

Componentes de una partida

¿Reducir los datos?

  • Algunas características, como el Supply, los valores de unidades o edificios del jugador que pierde caen rápidamente en un determinado momento de la partida.
  • En general, el jugador que gana tiene sus gráficas por encima de las del jugador contrario.

Extracción de información

  • XGBoost: biblioteca que implementa Gradient Boosting de manera eficiente y con gran rendimiento. Regularización evita sobreajuste.

Resultados con pendiente recta de regresión

Resultados con área bajo la curva

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Resultados con datos en crudo

Conclusiones

Conclusiones

  • La incertidumbre baja a lo largo de la partida
  • La elección de las características y del modelo han sido acertadas.

Trabajo futuro

  • Crear un bot competitivo utilizando características y un modelo de aprendizaje similares a los propuestos, mejorando la gestión de la incertidumbre que presentan bots anteriores, pudiendo adaptar mejor su estrategia o hacerlo en un momento anterior.
  • Combinar metaheurísticas y predicción del ganador para acelerar la ejecución de los algoritmos. Por ejemplo, dando una partida por resuelta mucho antes de que termine realmente.

Referencias